package com.lzy.arithmetic;

import java.util.HashSet;
import java.util.Set;

/**
 * Author: lzy
 * Date:   2020/06/09 14:30
 * Description:
 **/
public class 无重复字符的最长子串 {

    public static int lengthOfLongestSubstring(String s) {
        //哈希集合，去重，记录每个字符是否出现过
        Set<Character> occ = new HashSet<>();
        int n = s.length();
        // 右指针，初始值为-1，相当于我们在字符串左侧边界，还没有向右移动呢
        int rk = 0;
        // 返回的个数
        int ans = 0;
        //最长字符串左右指针
        int left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            // 左指针向右移动一格，移除一个字符
            if (i != 0) {
                occ.remove(s.charAt(i - 1));
            }
            while (rk < n && !occ.contains(s.charAt(rk))) {
                // 不断移动右指针
                occ.add(s.charAt(rk));
                rk++;
            }

            //存储最长字符串左右指针
            if (rk - i > ans) {
                left = i;
                right = rk;
            }

            //更新最大长度，从i到rk个字符是一个最长的无重复字符串
            ans = Math.max(ans, rk - i);
        }

        System.out.println("最长子串为：" + s.substring(left, right));
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abccbcda"));
    }
}
